#!/usr/bin/python3
# -*- coding: utf-8 -*-
# @author: zzll0909
# @file: 206.py
# @time: 2022/12/05
# @software: VS Code
from typing import Optional


class ListNode:
    def __init__(self, val=0, next=None):
        self.val = val
        self.next = next


class Solution:
    def reverseList(self, head: Optional[ListNode]) -> Optional[ListNode]:
        # 双指针迭代法
        prev = None
        node = head
        while node is not None:
            # 每次将node.next指向prev
            # 然后node和prev向后移动一次
            temp = node.next
            node.next = prev
            prev = node
            node = temp
        return prev


if __name__ == "__main__":
    node_1 = ListNode()
    node_1.val = 1
    node_2 = ListNode()
    node_2.val = 2
    node_1.next = node_2
    node_3 = ListNode()
    node_3.val = 3
    node_2.next = node_3
    node_4 = ListNode()
    node_4.val = 4
    node_3.next = node_4
    node_5 = ListNode()
    node_5.val = 5
    node_4.next = node_5
    solu = Solution()
    node = solu.reverseList(node_1)
    while node is not None:
        print(node.val)
        node = node.next
